1. Field of the Invention
The present invention relates to cryptographic scheme employed in various communication services using a computer network, such as home banking, firm banking, electronic mail service and electronic conference.
More particularly, the present invention is concerned with cryptographic scheme which conducts encryption of data to transmit and decryption of received cryptogram by using a computation in which two integers A and B are multiplied with each other and the product is divided by a third integer N to determine the residue, i.e., modular multiplication expressed by A.multidot.B mod N, as well as a computation known as modular exponentiation which is expressed by C=M.sup.e mod N(C,M,N,e), where E, M, N and e are integers and which is executed by repeating the above-mentioned modular multiplication.
Still more particularly, the present invention is concerned with a communication system which conducts cryptic communication by employing various cryptosystems such as RSA cryptosystem, ElGamal cryptosystem, DH type public key distribution system, ID-based key sharing cryptosystem and zero-knowledge certificate cryptosystem.
2. Description of the Related Art
In recent years, communication systems using computer networks have made a rapid progress, which has given a rise to the demand for cryptographic schemes employed for the purpose of protecting data contents. High-speed cryptographic schemes are essential in the current trends for greater capacity and higher communication speeds of networks.
Modular exponentiation and modular multiplication are very important computations which are used in various cryptographic schemes. For instance, these computations are used as follows.
It is known that criptosystem is classified into two types: namely, public-key criptosystem and common-key criptosystem. The public-key cryptosystem employs different keys for encryption and decryption. An encryption key is opened to public, while decryption key is kept confidential. With this system, it is easy to administrate keys but it is difficult to infer the decryption key from the opened encryption key. Cryptosystems which are based on modular exponentiation and modular multiplication, such as RSA cryptosystem and ElGamal cryptosystem are used most often as the public-key cryptosystem.
It has been noted that public-key cryptosystem has a specific use known as authentication, besides the confidential communication function. Authentication is a function to confirm whether the transmitter of a message is true and, hence, is referred to also as digital signature. The digital signature using a cryptosystem avoids any unjust transmission or forgery because the signature is put in terms of a secret key which is known only to the person who sends the message. This system is therefore broadly used as authenticated communication system in banking and financial businesses.
As a kind of common-key cryptosystem in which both the person who transmits the message and the person who receives the message commonly possess a key in confidence, known is barnum cryptosystem in which a random number is added to data. The random number used for such a purpose may be a random number known as square residue obtained on the basis of modular exponentiation and modular multiplication.
Such common-key cryptosystem and open-key cryptosystem are often used together with an art known as key distribution system or an art known as key-sharing system. Among various key distribution systems, most popular is DH type key distribution system proposed by Diffie and Hellman. This distribution system also employs modular exponentiation and modular multiplication. Meanwhile, ID-based key sharing system has been noticed among the key sharing systems. Modular exponentiation and modular multiplication are also employed in this key sharing system, as well as in most of other key sharing systems.
Cryptographic scheme also includes an art which is referred to as zero knowledge certificate. This art is to enable a person to make the opponent be convinced of the fact that the person actually possesses a knowledge, without disclosing at all the content of the knowledge, i.e., with zero knowledge. Various procedures based on modular exponentiation and modular multiplication are available in this art.
Under these circumstances, there has been an increasing demand for circuits which perform efficient modular exponentiation and modular multiplication, in order to make it possible to efficiently build up various cryptosystems. Such high-speed modular exponentiation and modular multiplication circuits also contribute to increase in the speed of various cryptosystems.
As a method of conducting modular multiplication computation using N as a modulus, a method is known which uses an integer R which is prime to N. For instance, Montgomery, P. L.: "Modular multiplication without trial division" Math. of Computation, Vol. 44, 1985, pp. 519-521 makes it possible to conduct modular multiplication without division, by computing Q=A.multidot.B.multidot.R.sup.-1 mod N instead of computing Q=A.multidot.B mod N.
Another technique for achieving higher processing speed is a method referred to as parallel processing, a typical example of architecture of which is systolic array as well known. Systolic array executes pipeline-based processing using a plurality of types of processing elements (PE), thus realizing a high-speed processing. Furthermore, the control can easily be conducted locally on PE basis. Thus, systolic array possesses both the regularity of the whole structure and locality on PE basis and is known as an architecture which facilitates construction of a large scale processing device such as a VLSI. The parallel processing is considered as being most suitable for speeding up of modular exponentiation and modular multiplication on a large integer which requires a very large scale of processing. Hitherto, however, almost no architecture has been proposed as to application of parallel processing technique such as systolic array for modular exponentiation and modular multiplication.
An array using Montgomery technique has been proposed by Even. (see Shimon Even: "Systolic modular multiplication, "Advances in Cryptology-CRYPTO'90, pp. 619-624, Springer-Verlag.)
In order to obtain sufficient security against cryptanalysis for a wrong purpose, the integer used in modular exponentiation and modular multiplication should have a large number of bits which is 512 or greater. Computational complexity for such a large integer is huge and cannot be dealt with at high speed by an ordinary computer.
Another problem is that, when modular exponentiation is executed by repetition of the Montgomery method, the maximum bit number of the output is progressively increased each time the modular multiplication is conducted, so that it is difficult to execute modular exponentiation by a single circuit. The array proposed by Even does not contain any suggestion concerning PE which would conduct processing when the bit number of the output of modular multiplication has exceeded the bit number of the input value and, hence, cannot fully perform modular exponentiation.
Furthermore, known Montgomery method requires, as will be detailed later, that separate computations are conducted on A, B and Q before computing Q=A.multidot.B.multidot.R.sup.-1 mod N, thus necessitating a plurality of computing means.
In particular, the array proposed by Even is composed of an array which performs a multiplication T=A.multidot.B and an array which performs a modular multiplication Q=T.multidot.R.sup.-1 mod N on R which is treated as a constant. Thus, the systolic array of Even was inefficient in that it essentially employ two types of arrays: one for computing T and other for computing Q. In addition, the systolic array proposed by Even has inferior adaptability because it performs only 1-bit based computation is performed in PE.
Thus, the known methods involve various drawbacks and cannot provide efficient modular multiplication circuit.